package Heap;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:模拟通过大根堆实现优先级队列
 * User: 阿宾
 * Date: 2024-12-07
 * Time: 09:55
 */
public class MyHeap {
    private int[] elem;//使用数组存储堆元素
    private int size;//记录数组的有效长度

    public MyHeap(){
        //初始化10个内存空间
        this.elem = new int[10];
    }
    public void InitHeap(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            size++;
        }
    }


    //建堆
    //从完全二叉树的分支节点开始向上调整每一个二叉树，直到将所有二叉树调整成大根堆
    public void BuildMaxHeap(){
        //将元素位置从0开始计数，而不是从1
        for (int i = (size-1)/2; i >= 0 ; i--) {
            //从分支节点开始调整，将所有子树调整为大根堆
            AdjustDown(i,size);
        }
    }

    //将以数组下标为k的为根节点的子树向下调整成大根堆
    private void AdjustDown(int k, int size) {
        int i = 0;
        for (i = 2*k+1;  i < size ; i=i*2+1) {
            //i+1<size是防止数组越界
            if (i + 1 < size && elem[i] < elem[i + 1]) {
                i++;
            }
            //此时i指向的就是最大的孩子节点下标，将最大孩子节点值与根节点值比较
            if (elem[k] > elem[i]) {
                //根节点值比孩子节点值大，符合大根堆，直接跳出循环
                break;
            } else {
                //更新根节点的值，同时更新根节点的指向，
                //继续调整左右子树根节点值最大的子树
                swap(k, i);
                k = i;
            }
        }
    }

    //插入元素
    public void offer(int val){
        //1.判断数组是否需要扩容
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        //2.将元素插入数组尾部
        this.elem[size] = val;
        //3.向上调整子树为大根堆
        AdjustUp(size);
        //4.修改数组大小
        size++;
    }
    //向上调整，调整以下标为child元素作为根节点的子树为大根堆
    private void AdjustUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;
                parent = (parent-1)/2;
            } else {
                break;
            }
        }
    }
    private void swap(int i,int j) {
        int tmp = elem[i];
        elem[i] = elem[j];
        elem[j] = tmp;
    }

    //判断是否满
    public boolean isFull() {
        return size == elem.length;
    }

    //删除元素
    public int poll(){
        //1.接收数组尾部元素
        int ret = elem[size-1];
        //2.将尾部元素与首元素交换
        swap(0,size-1 );
        //3.修改数组大小
        size--;
        //4.向下调整以k为根节点子树为大根堆
        AdjustDown(0,size);
        //5.返回删除元素
        return ret;
    }

    //查看堆顶元素
    public int peek() {
        return elem[0];
    }
    //获取有效元素个数
    public int size(){
        return this.size;
    }
    //判断数组是否为空
    public boolean isEmpty(){
        return this.size == 0;
    }

    //堆排序
    public void HeapSort(){
        //建立大根堆
        BuildMaxHeap();
        //开始排序
        for (int i = size-1; i > 0 ; i--) {
            swap(i,0);
            AdjustDown(0,i);
        }
    }
}
